//给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 
//
// 示例 1: 
//
// 输入: "(()"
//输出: 2
//解释: 最长有效括号子串为 "()"
// 
//
// 示例 2: 
//
// 输入: ")()())"
//输出: 4
//解释: 最长有效括号子串为 "()()"
// 
// Related Topics 字符串 动态规划


package leetcode.d_1_99;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

// https://leetcode.cn/problems/longest-valid-parentheses/
//Java：最长有效括号
public class P32LongestValidParentheses{
    public static void main(String[] args) {
        P32LongestValidParentheses solution = new P32LongestValidParentheses();
        System.out.println(solution.longestValidParentheses(")()())")); // 4
    }

    // 栈的解法
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        if (s.length() == 0) {
            return 0;
        }
//        Stack<Integer> stack = new Stack();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        char[] chars = s.toCharArray();
        for(int i=0; i<chars.length; i++) {
            if (chars[i] == '(') {
                // 入栈
                stack.push(i);
            }
            if (chars[i] == ')') {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                }else {
                    int preIdx = stack.peek();
                    maxLen = Math.max(maxLen, i-preIdx);
                }
            }
        }
        return maxLen;
    }

    public int longestValidParentheses2(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        char[] charArray = s.toCharArray();
        int len = charArray.length;

        // int[i] = 有效括号字符串的最大长度
        int[] dp = new int[len];
        int max = 0;
        for (int i = 1; i < len; i++) {
            if (charArray[i] == ')'){
                //只有最后一个是）才有效
                if (charArray[i-1] == '('){
                    //倒数第2个数（
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }else {
                    //倒数第2个数）
                    if (i - dp[i-1] > 0 && charArray[i-dp[i-1]-1] == '('){
                        dp[i] = (dp[i - 1] + 2) + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) ;
                    }
                }
                max = Math.max(dp[i], max);
            }
        }
        return max;
    }

}